package com.yubest;

/**
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * 示例 2：
 * <p>
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 * 示例 3：
 * <p>
 * 输入：nums1 = [0,0], nums2 = [0,0]
 * 输出：0.00000
 * 示例 4：
 * <p>
 * 输入：nums1 = [], nums2 = [1]
 * 输出：1.00000
 * 示例 5：
 * <p>
 * 输入：nums1 = [2], nums2 = []
 * 输出：2.00000
 *  
 * <p>
 * 提示：
 * <p>
 * nums1.length == m
 * nums2.length == n
 * 0 <= m <= 1000
 * 0 <= n <= 1000
 * 1 <= m + n <= 2000
 * -10^6 <= nums1[i], nums2[i] <= 10^6
 *  
 * <p>
 * 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/10/18 17:59
 */
public class P0004 {

    public static void main(String[] args) {
        int[] nums1 = {1, 3}, nums2 = {2};
        System.out.println(new Solution4().findMedianSortedArrays(nums1, nums2));

        int[] nums3 = {1, 2}, nums4 = {3, 4};
        System.out.println(new Solution4().findMedianSortedArrays(nums3, nums4));

        int[] nums5 = {0, 0}, nums6 = {0, 0};
        System.out.println(new Solution4().findMedianSortedArrays(nums5, nums6));

        int[] nums7 = {}, nums8 = {1};
        System.out.println(new Solution4().findMedianSortedArrays(nums7, nums8));

        int[] nums9 = {2}, nums10 = {};
        System.out.println(new Solution4().findMedianSortedArrays(nums9, nums10));
    }
}

class Solution4 {

    /**
     * 思路：双指针移动算法
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null) {
            nums1 = new int[0];
        }
        if (nums2 == null) {
            nums2 = new int[0];
        }
        int len = nums1.length + nums2.length;
        //数组nums1对应的指针
        int pointer1 = -1;
        //数组nums2对应的指针
        int pointer2 = -1;
        //n1, n2为用于计算中位数的两个值
        //最近指针指向的元素值，存储上一次遍历计算出的最大值
        int n1 = 0;
        //最新指针指向的元素值，存储最新一次遍历计算出的最大值
        int n2 = 0;
        for (int i = 0; i < len / 2 + 1; i++) {
            //n1始终存储n2的旧值
            n1 = n2;
            //如果pointer1指向数组最后一个元素，只递增pointer2指针
            if (pointer1 == nums1.length - 1) {
                pointer2++;
                n2 = nums2[pointer2];
            }
            //如果pointer2指向数组最后一个元素，只递增pointer1指针
            else if (pointer2 == nums2.length - 1) {
                pointer1++;
                n2 = nums1[pointer1];
            }
            //pointer1和pointer2未指向数组最后一个元素，找出两个指针，当前指向的最小值，指针向前移动并且n2赋最新值
            else if (nums1[pointer1 + 1] > nums2[pointer2 + 1]) {
                pointer2++;
                n2 = nums2[pointer2];
            } else {
                pointer1++;
                n2 = nums1[pointer1];
            }
        }
        if (len == 0) {
            return 0.0;
        } else if (len == 1) {
            return n2 * 1.0;
        } else {
            //如果为偶数个元素，对n1 + n2计算中位数，如果为奇数个元素，n2即是中位数
            return len % 2 == 0 ? (n1 + n2) / 2.0 : n2 * 1.0;
        }
    }
}
